#include <vector>
#include <iostream>

using namespace std;

/*
amount：总钱数
limit: 给出的最多硬币数
coins: 硬币的面额
返回：硬币的组合数
*/
/*
coins = [10, 50, 100, 500]
amount = 1000
limit = 15

🖐
i = amount / 500 如果我们用 500 的硬币去组合 amount ，我们可以用多少枚
500
makingChange(amount - 500 * i, limit - i, [10, 50, 100])

100
makingChange(amount - 100 * i, limit - i, [10, 50])


...

amount / coin <= limit

coins = [10, 50, 100]
*/
int makingChange(int amount, int limit, vector<int> coins) {
  int result = 0;
  int coin = coins.back();
  coins.pop_back();

  if (coins.size() == 0) {
    if (amount / coin <= limit) {
      return 1;
    }
  }
  else {
    for (int i = 0; i <= amount / coin; ++i) {
      result += makingChange(amount - coin * i, limit - i, coins);
    }
  }

  return result;
}

int main(int argc, char const *argv[])
{
  /* code */
  vector<int> coins {10, 50, 100, 500};
  cout << makingChange(1000, 15, coins) << endl;

  return 0;
}
